
两个指针可能指向同一个存储单元，在这一点上它们彼此别名。内存在LLVM模型中没有类型，这使得优化器很难确定两个指针是否相互别名。若编译器可以证明两个指针不会相互别名，就可以进行更多的优化。在下一节中，我们将更深入地研究这个问题，并研究在实现这种方法之前添加元数据将有什么好处。

\mySubsubsection{6.2.1.}{理解对元数据的需求}

为了演示这个问题，来看看下面的函数:

\begin{cpp}
void doSomething(int *p, float *q) {
    *p = 42;
    *q = 3.1425;
}
\end{cpp}

优化器不能决定指针p和q是否指向相同的内存单元。优化过程中，可以执行一个重要的分析，称为别名分析。若p和q指向相同的存储单元，其互为别名。此外，若优化器可以证明两个指针永远不会相互别名，这就提供了优化机会。例如，在doSomething()函数中，存储可以在不改变结果的情况下重新排序。

此外，若一种类型的变量可以是另一种不同类型变量的别名，则取决于源语言的定义。注意，语言也可能包含不基于类型的别名假设的表达式——例如，不相关类型之间的类型强制转换。

LLVM开发人员选择的解决方案是在加载和存储指令中添加元数据。添加的元数据有两个目的:

\begin{itemize}
\item
首先，定义了类型层次结构，在此基础上类型可以别名另一个类型

\item
其次，描述了加载或存储指令中的内存访问
\end{itemize}

来看一下C中的类型层次结构。每种类型的层次结构都从一个根节点开始，可以命名，也可以匿名。LLVM假设具有相同名称的根节点描述相同类型的层次结构，可以在相同的LLVM模块中使用不同的类型层次结构，并且LLVM可以安全地假设这些类型可以别名。在根节点下面是标量类型的节点，聚合类型的节点不添加到根节点，但会引用标量类型和其他聚合类型。Clang定义C语言的层次结构如下:

\begin{itemize}
\item
根节点称为简单的C/C++ TBAA。

\item
根节点下面是用于字符类型的节点。这是C语言中的一种特殊类型，所有指针都可以转换为指向char的指针。

\item
char节点下面是其他标量类型的节点和所有指针的类型，称为any指针。
\end{itemize}

除此之外，聚合类型可定义为成员类型和偏移量的序列。

这些元数据定义会添加到加载和存储指令的访问标记中。访问标记由三部分组成:基本类型、访问类型和偏移量。根据基本类型的不同，访问标签描述内存访问有两种可能的方式:

\begin{enumerate}
\item
若基类型是聚合类型，则访问标记描述具有必要访问类型的struct成员的内存访问，并位于给定的偏移量。

\item
若基类型是标量类型，则访问类型必须与基类型相同，并且偏移量必须为0。
\end{enumerate}

有了这些定义，就可以在访问标记上定义一个关系，用于计算两个指针是否可以相互别名。来仔细看看(基类型，偏移量)元组的直接父对象的选项:

\begin{enumerate}
\item
若基类型是标量类型且偏移量为0，则直接父类型为(父类型，0)，父类型为父节点的类型，如类型层次结构中定义的那样。若偏移量不为0，则父级未定义。

\item
若基类型是聚合类型，则(基类型，偏移量)元组的直接父级是(新类型，新偏移量)元组，新类型是偏移量处成员的类型。新偏移量是新类型的偏移量，调整到其新起点。
\end{enumerate}

这个关系的传递闭包就是父关系。两个内存访问(基类型1，访问类型1，偏移量1)和(基类型2，访问类型2，偏移量2)，若(基类型1，偏移量1)和(基类型2，偏移量2)在父关系中相关，则相互别名，反之亦然。

用一个例子来说明这一点:

\begin{cpp}
struct Point { float x, y; }
void func(struct Point *p, float *x, int *i, char *c) {
    p->x = 0; p->y = 0; *x = 0.0; *i = 0; *c = 0;
}
\end{cpp}

当使用标量类型的内存访问标记定义时，i参数的访问标记是(int, int, 0)，而c参数的访问标记是(char, char, 0)。类型层次结构中，int类型的节点的父节点是char节点，所以(int, 0)的直接父指针是(char, 0)，并且两个指针都可以别名。对于x和c参数也是如此，但x和i参数是不相关的，所以它们不会相互别名。对结构体Point的y成员的访问是(Point, float, 4)，其中4是该结构体中y成员的偏移量。(Point, 4)的直接父变量是(float, 0)，所以对p->y和x的访问可以别名；同理，参数c也可以使用别名。

\mySubsubsection{6.2.2.}{LLVM中创建TBAA元数据}

创建元数据，必须使用llvm::MDBuilder类，在llvm/IR/MDBuilder.h头文件中声明。数据本身存储在llvm::MDNode和llvm::MDString类的实例中，使用builder类可以避免我们了解构造的内部细节。

通过createTBAARoot()方法创建根节点，该方法需要将类型层次结构的名称作为参数，并返回根节点。可以使用createAnonymousTBAARoot()方法创建一个匿名的唯一根节点。

使用createTBAAScalarTypeNode()方法将标量类型添加到层次结构中，该方法将类型的名称和父节点作为参数。

另一方面，为聚合类型添加类型节点稍微复杂一些。createTBAAStructTypeNode()方法接受类型的名称和字段列表作为参数。具体来说，字段以std::pair<llvm::MDNode*, uint64\_t>实例的形式给出，其中第一个元素表示成员的类型，第二个元素表示struct中的偏移量。

使用createTBAAStructTagNode()方法创建访问标记，该方法将基类型、访问类型和偏移量作为参数。

最后，元数据必须附加到加载或存储指令。Instruction类包含一个名为setMetadata()的方法，该方法用于添加各种基于类型的别名分析元数据。第一个参数必须是llvm::LLVMContext::MD\_tbaa类型，第二个参数必须是访问标签。

有了这些知识，就可以向tinylang添加用于基于类型的别名分析(TBAA)的元数据了。

\mySubsubsection{6.2.3.}{tinylang中添加TBAA元数据}

为了支持TBAA，必须添加一个新的CGTBAA类，该类负责生成元数据节点。此外，我们使CGTBAA类成为CGModule类的成员，称其为TBAA。

每条加载和存储指令都必须加注解，为此在CGModule类中创建了一个名为decorateInst()的新函数，这个函数尝试创建标记访问信息。若成功，则元数据将添加到相应的加载或存储指令。此外，这种设计还允许在不需要的情况下关闭元数据生成过程，例如在构建中关闭优化:

\begin{cpp}
void CGModule::decorateInst(llvm::Instruction *Inst,
                            TypeDeclaration *Type) {
    if (auto *N = TBAA.getAccessTagInfo(Type))
        Inst->setMetadata(llvm::LLVMContext::MD_tbaa, N);
}
\end{cpp}

我们将新CGTBAA类的声明放在include/tinylang/CodeGen/CGTBAA.h头文件中，并将定义放在lib/CodeGen/CGTBAA.cpp文件中。除了AST定义，头文件还需要包含定义元数据节点和构建器的文件:

\begin{cpp}
#include "tinylang/AST/AST.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/Metadata.h"
\end{cpp}

CGTBAA类需要存储一些数据成员:

\begin{enumerate}
\item
首先，需要缓存类型层次结构的根:

\begin{cpp}
class CGTBAA {
    llvm::MDNode *Root;
\end{cpp}

\item
为了构造元数据节点，需要一个MDBuilder类的实例:

\begin{cpp}
    llvm::MDBuilder MDHelper;
\end{cpp}

\item
最后，必须存储为一个类型生成的元数据以供重用:

\begin{cpp}
    llvm::DenseMap<TypeDenoter *, llvm::MDNode *> MetadataCache;
    // …
};
\end{cpp}
\end{enumerate}

现在已经定义了构造所需的变量，必须添加创建元数据所需的方法:

\begin{enumerate}
\item
构造函数初始化数据成员:

\begin{cpp}
CGTBAA::CGTBAA(CGModule &CGM)
    : CGM(CGM),
    MDHelper(llvm::MDBuilder(CGM.getLLVMCtx())),
    Root(nullptr) {}
\end{cpp}

\item
必须惰性地实例化类型层次结构的根，将其命名为Simple tinylang TBAA:

\begin{cpp}
llvm::MDNode *CGTBAA::getRoot() {
    if (!Root)
        Root = MDHelper.createTBAARoot("Simple tinylang TBAA");
    return Root;
}
\end{cpp}

\item
对于标量类型，必须在MDBuilder类的帮助下根据类型的名称创建元数据节点。新的元数据节点存储在缓存中:

\begin{cpp}
llvm::MDNode *
CGTBAA::createScalarTypeNode(TypeDeclaration *Ty,
                            StringRef Name,
                            llvm::MDNode *Parent) {
    llvm::MDNode *N =
        MDHelper.createTBAAScalarTypeNode(Name, Parent);
    return MetadataCache[Ty] = N;
}
\end{cpp}

\item
为记录创建元数据的方法更加复杂，所以必须枚举记录的所有字段。与标量类型类似，新的元数据节点存储在缓存中:

\begin{cpp}
llvm::MDNode *CGTBAA::createStructTypeNode(
        TypeDeclaration *Ty, StringRef Name,
        llvm::ArrayRef<std::pair<llvm::MDNode *, uint64_t>> Fields) {
    llvm::MDNode *N =
        MDHelper.createTBAAStructTypeNode(Name, Fields);
    return MetadataCache[Ty] = N;
}
\end{cpp}

\item
要返回tinylang类型的元数据，需要创建类型层次结构。由于tinylang的类型系统非常有限，可以使用一种简单的方法。每个标量类型都是映射到根节点的唯一类型，并且将所有指针映射到单个类型，再结构化类型引用这些节点。若不能映射类型，则返回nullptr:

\begin{cpp}
llvm::MDNode *CGTBAA::getTypeInfo(TypeDeclaration *Ty) {
    if (llvm::MDNode *N = MetadataCache[Ty])
        return N;

    if (auto *Pervasive =
            llvm::dyn_cast<PervasiveTypeDeclaration>(Ty)) {
        StringRef Name = Pervasive->getName();
        return createScalarTypeNode(Pervasive, Name, getRoot());
    }
    if (auto *Pointer =
            llvm::dyn_cast<PointerTypeDeclaration>(Ty)) {
        StringRef Name = "any pointer";
        return createScalarTypeNode(Pointer, Name, getRoot());
    }
    if (auto *Array =
            llvm::dyn_cast<ArrayTypeDeclaration>(Ty)) {
        StringRef Name = Array->getType()->getName();
        return createScalarTypeNode(Array, Name, getRoot());
    }
    if (auto *Record =
            llvm::dyn_cast<RecordTypeDeclaration>(Ty)) {
        llvm::SmallVector<std::pair<llvm::MDNode *, uint64_t>,
        4> Fields;
        auto *Rec =
            llvm::cast<llvm::StructType>(CGM.convertType(Record));
        const llvm::StructLayout *Layout =
        CGM.getModule()->getDataLayout().getStructLayout(Rec);

        unsigned Idx = 0;
        for (const auto &F : Record->getFields()) {
            uint64_t Offset = Layout->getElementOffset(Idx);
            Fields.emplace_back(getTypeInfo(F.getType()), Offset);
            ++Idx;
        }
        StringRef Name = CGM.mangleName(Record);
        return createStructTypeNode(Record, Name, Fields);
    }
    return nullptr;
}
\end{cpp}

\item
获取元数据的一般方法是getAccessTagInfo()。要获取TBAA访问标记信息，必须添加对getTypeInfo()函数的调用。这个函数期望TypeDeclaration作为它的参数，可从生成元数据的指令中检索:

\begin{cpp}
llvm::MDNode *CGTBAA::getAccessTagInfo(TypeDeclaration *Ty) {
    return getTypeInfo(Ty);
}
\end{cpp}

\end{enumerate}

最后，为了生成TBAA元数据，只需要将元数据添加到tinylang中成的所有加载和存储指令上即可。

例如，在CGProcedure:: writvariable()中，存储一个全局变量使用一个存储指令:

\begin{cpp}
    Builder.CreateStore(Val, CGM.getGlobal(D));
\end{cpp}

为了修饰这个特定的指令，需要用以下几行替换这一行，其中decorateInst()将TBAA元数据添加到这个存储指令中:

\begin{cpp}
    auto *Inst = Builder.CreateStore(Val, CGM.getGlobal(D));
    // NOTE: V is of the VariableDeclaration class, and
    // the getType() method in this class retrieves the
    // TypeDeclaration that is needed for decorateInst().
    CGM.decorateInst(Inst, V->getType());
\end{cpp}

有了这些更改，就完成了TBAA元数据的生成。

现在，可以将示例tinylang文件编译为LLVM中间表示，以查看新实现的TBAA元数据。例如，以下文件Person.mod:

\begin{shell}
MODULE Person;

TYPE
    Person = RECORD
                Height: INTEGER;
                Age: INTEGER
             END;

PROCEDURE Set(VAR p: Person);
BEGIN
    p.Age := 18;
END Set;

END Person.
\end{shell}

本章的构建目录中构建的tinylang编译器可以用来生成这个文件的中间表示:

\begin{shell}
$ tools/driver/tinylang -emit-llvm ../examples/Person.mod
\end{shell}

新生成的Person.ll文件中，可以看到存储指令是用本章中生成的TBAA元数据，其中元数据反映了最初声明的记录类型的字段:

\begin{shell}
; ModuleID = '../examples/Person.mod'
source_filename = "../examples/Person.mod"
target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
target triple = "arm64-apple-darwin22.6.0"

define void @_t6Person3Set(ptr nocapture dereferenceable(16) %p) {
entry:
    %0 = getelementptr inbounds ptr, ptr %p, i32 0, i32 1
    store i64 18, ptr %0, align 8, !tbaa !0
    ret void
}

!0 = !{!"_t6Person6Person", !1, i64 0, !1, i64 8}
!1 = !{!"INTEGER", !2, i64 0}
!2 = !{!"Simple tinylang TBAA"}
\end{shell}

既然了解了如何生成TBAA元数据，我们将在下一节中探索一个非常相似的主题:生成调试元数据。

























